package brinaryTree;

public class N236_LowestCommonAncestorOfABinaryTree {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果p q任意一个节点等于root，那么root就是最近公共祖先，直接返回，如果root是空，那也直接返回
        if (p == root || q == root || root == null) return root;

        // 求左右子树的拿到的p q 最近公共祖先
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 如果 左右拿到的最近公共祖先不一样，那该节点就是最近公共祖先
        if (left != null && right != null) return root;
        // 如果有一个为空，那不为空的那个是最近祖先
        if (left == null && right != null) return right;
        else if (left != null && right == null) return left;
        // 都为空，都不是
        else return null;
    }
}
